package com.wfm.leetcode.editor.cn;

import com.wfm.alg.P线段树;
import com.wfm.alg.P线段树.SegTreeDynamic;
import com.wfm.alg.P线段树.SegTreeDynamic.Node;

public class PSeven31我的日程安排表II{
//leetcode submit region begin(Prohibit modification and deletion)
class MyCalendarTwo {


    public MyCalendarTwo() {

    }
    
    public boolean book(int start, int end) {
        if(querySumMax(root,0,N,start,end-1)==2){
            return false;
        }
        updateSumMax(root,0,N,start,end-1,1);
        return true;
    }

    public class Node {
        Node left, right;
        int val, add;
    }
    public int N = (int) 1e9;
    public Node root = new Node();

    public void updateSumMax(Node node, int start, int end, int l, int r, int val) {
        if (l <= start && end <= r) {
            node.val += val;
            node.add += val;
            return ;
        }
        int mid = (start + end) >> 1;
        pushDown1(node);
        if(r<=mid){
            updateSumMax(node.left,start,mid,l,r,val);
        }else if(l>mid){
            updateSumMax(node.right,mid+1,end,l,r,val);
        }else {
            updateSumMax(node.left,start,mid,l,mid,val);
            updateSumMax(node.right,mid+1,end,mid+1,r,val);
        }
        node.val = Math.max(node.left.val , node.right.val);
    }

    // 在区间 [start, end] 中查询区间 [l, r] 的结果，即 [l ,r] 保持不变
    public int querySumMax(Node node, int start, int end, int l, int r) {
        if (l <= start && end <= r) return node.val;
        int mid = (start + end) >> 1, ans = 0;
        pushDown1(node);
        if(r<=mid){
            ans =  querySumMax(node.left,start,mid,l,r);
        }else if(l>mid){
            ans = querySumMax(node.right,mid+1,end,l,r);
        }else {
            ans=Math.max(querySumMax(node.left,start,mid,l,mid),
                    querySumMax(node.right,mid+1,end,mid+1,r));
        }
        return ans;
    }

    private void pushDown1(Node node) {
        // 动态开点 如果节点没有左右子节点，先开个没有值的节点
        if (node.left == null) node.left = new Node();
        if (node.right == null) node.right = new Node();
        if (node.add == 0) return ;
        node.left.val += node.add;
        node.right.val += node.add;

        node.left.add += node.add;
        node.right.add += node.add;
        node.add = 0;
    }
}

/**
 * Your MyCalendarTwo object will be instantiated and called as such:
 * MyCalendarTwo obj = new MyCalendarTwo();
 * boolean param_1 = obj.book(start,end);
 */
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        MyCalendarTwo solution = new PSeven31我的日程安排表II().new MyCalendarTwo();
        System.out.println(solution.book(10, 20));
        System.out.println(solution.book(50, 60));
        System.out.println(solution.book(10, 40));
        System.out.println(solution.book(5, 15));
        System.out.println(solution.book(5, 10));
        System.out.println(solution.book(25, 55));
    }
}